513. Проблема Николая

Николаю нужно доставить подарки для n (n ≤ 10¹⁸) детей. Его интересует, сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю m (m ≤ 2009).

Вход. В одной строке заданы два натуральных числа n и m.

Выход. Вывести искомое количество способов.

Пример входа	Пример выхода
5 1000	120

РЕШЕНИЕ

элементарная задача

Анализ алгоритма

Искомое количество способов доставки подарков равно n! mod m. Если m ≤ n, то m входит как множитель в n!. В этом случае n! mod m = 0.

Иначе (при n < m) вычисляем значение выражения n! mod m при помощи цикла. При этом количество итераций будет не более n < m ≤ 2009.

Пример

100! mod 77 = (1 * 2 * … * 76 * 77 * 78 * … * 100) mod 77 = 0, так как 100! делится на 77.

Реализация алгоритма

Читаем входные данные.

scanf("%lld %lld",&n,&m);

Если m ≤ n, то ответ равен 0.

if (n >= m) res = 0; else

{

Иначе n < m ≤ 2009, вычисляем значение n! mod m при помощи цикла.

for(res = i = 1; i <= n; i++)

res = (res * i) % m;

}

Выводим ответ.

printf("%lld\n",res);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n = con.nextLong();

long m = con.nextLong();

long res = 1;

if (n >= m) res = 0; else

{

for(long i = 1; i <= n; i++)

res = (res * i) % m;

}

System.out.println(res);

con.close();

}

}

Python реализация

n, m = map(int,input().split())

if n >= m: res = 0

else:

res = 1

for i in range (1, n+1):

res = (res * i) % m

print(res)